/*
 * 百度在线网络技术（北京）有限公司拥有本软件版权2021并保留所有权利。
 * Copyright 2021, Baidu.com,Inc 2:Baidu Online Network Technology (Beijing) Co.,Ltd,
 * All rights reserved.
 */

package com.azdebugit.map.est;


import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import com.azdebugit.test.collection.CommandUtil;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class BinaryMapTest {
    private static Logger logger = LoggerFactory.getLogger(BinaryMapTest.class.getSimpleName());
    /**
     * @Description 生成树形结构nodeTree; List tagList原始无序数据链表
     * @auther: wz
     * @date: 2019/1/18 15:09
     */
    private List<TagBinaryTree> createNodeTree(List tagList) {
        long beginTime = System.currentTimeMillis();
        logger.info("节点树构型开始---时间:" + beginTime);
        Iterator<Tag> iterable = tagList.iterator();
        List<TagBinaryTree> finalList = new ArrayList();
        List<TagBinaryTree> remainList = new ArrayList<>();//没找到父节点的节点集合
        while (iterable.hasNext()) {
            Tag tag1 = iterable.next();
            TagBinaryTree binaryTree = new TagBinaryTree(tag1, new ArrayList<TagBinaryTree>());
            if (tag1.getParentId() == 0) {//找出一级标签
                finalList.add(binaryTree);
                iterable.remove();//从集合中移除一级标签
            } else {
                boolean findResult = findNode(finalList, binaryTree);
                if (!findResult)
                    remainList.add(binaryTree);
            }
        }
        //处理剩余没找到父节点的节点 1.不会存在一级标签 2.不确定顺序
        //1.遍历剩余集合 自己匹配
        Iterator<TagBinaryTree> remainIterator = remainList.iterator();
        while (remainIterator.hasNext()) {
            TagBinaryTree remainNode = remainIterator.next();
            logger.info("");
            //自己匹配
            boolean Result = findNode(remainList, remainNode);
            if (Result) remainIterator.remove();
        }

        //2.匹配最终树
        Iterator<TagBinaryTree> remainIterator2 = remainList.iterator();
        while (remainIterator2.hasNext()) {
            TagBinaryTree remainNode = remainIterator2.next();
            boolean findResult = findNode(finalList, remainNode);
            if (findResult) remainIterator2.remove();
        }
        //处理之后还有剩余 余下节点将作为一级节点
        if (remainList.size() > 0) {
            logger.info("处理剩余节点后还有剩余,将节点添加到一级节点集合中");
            for (TagBinaryTree tagBinaryTree : remainList)
                finalList.add(tagBinaryTree);
        }
        long endTime = System.currentTimeMillis();
        logger.info("节点树构型结束---时间：" + endTime);
        logger.info("耗时：" + (endTime - beginTime));
        return finalList;
    }

    /**
     * @Description 遍历树 找到位置 递归
     * srcTreeList 树结构  目标节点 targetBinaryTree
     * @auther: wz
     * @date: 2019/1/18 12:35
     */
    private boolean findNode(List<TagBinaryTree> srcTreeList, TagBinaryTree targetBinaryTree) {
        Iterator iterator = srcTreeList.iterator();
        while (iterator.hasNext()) {
            TagBinaryTree node = (TagBinaryTree) iterator.next();
            Tag srcTag = node.getTag();
            Tag tarTag = targetBinaryTree.getTag();
            if (srcTag.getId().equals(tarTag.getParentId())) {//找到父节点 添加到父节点下
                List<TagBinaryTree> srcChildrenList = node.getChildrenList();
                srcChildrenList.add(targetBinaryTree);
                return true;
            } else {//查找该节点下的子节点
                boolean findChildrenNodeResult = findNode(node.getChildrenList(), targetBinaryTree);
                if (findChildrenNodeResult) return true;
            }
        }
        return false;
    }

}
